import java.util.Arrays;

public class Test {
    /**
     * 二分类型题可以简单进行总结如下
     * 1、分为两种模版，模版一就是针对答案在左边的情况，模版二就是针对答案在右边区间的情况
     * 2、如何使用呢？其实很多二分题都是带有提示的，一般说明是最大或者最小的或者最多最少的大部分情况都是可以用二分的
     * 3、如何选择？就像上面说的两个模版，比如最小最少就是答案肯定是趋于左边区间的，如下代码的左边情况就是左边答案，右边就是最大最多的类似情况，后续题目我也会补充
     * 4、简单说就是最小最少的就使用左边情况，最大最多使用右边情况
     * */

    //查找target在数组中第一次出现位置和最后一次出现的位置下标
    public int[] searchRange(int[] nums, int target) {
        int[] ret=new int[2];
        ret[0]=ret[1]=-1;
        //处理空数组情况
        if(nums.length==0){
            return ret;
        }
        int left=0,right=nums.length-1;
        //处理左边情况
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else {
                right=mid;
            }
        }
        //判断结果是否存在
        if(nums[left]!=target)return ret;
        else ret[0]=left;

        //处理右边情况
        right=nums.length-1;
        while(left<right){
            int mid=left+(right-left+1)/2;
            if(nums[mid]<=target){
                left=mid;
            }else{
                right=mid-1;
            }
        }

        ret[1]=right;
        return ret;
    }

    public static void main(String[] args) {
        int[] nums={5,7,7,8,8,10};
        int target=8;
        Test test=new Test();
        int[] ret=test.searchRange(nums,8);
        for(int i:ret){
            System.out.print(i+" ");
        }
//        System.out.println();
//        System.out.println(Arrays.toString(test.searchRange(nums, target)));
    }
}
